/*
 * @Author: liusheng
 * @Date: 2022-04-26 20:22:32
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-26 21:08:49
 * @Description: 剑指 Offer II 046. 二叉树的右侧视图
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 
 剑指 Offer II 046. 二叉树的右侧视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

 

示例 1:
          1
         / \
        2   3
         \   \  
          5   4 


输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:

输入: [1,null,3]
输出: [1,3]
示例 3:

输入: []
输出: []
 

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100 
 

注意：本题与主站 199 题相同：https://leetcode-cn.com/problems/binary-tree-right-side-view/
 */
#include "header.h"
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*
use queue to traverse by level,record the last node in every level
*/
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root)
        {
            return {};
        }

        queue<TreeNode *> levelNodeQ;
        levelNodeQ.push(root);

        vector<int> rightSightVals;
        while (!levelNodeQ.empty())
        {
            int curLevelNodeNum = levelNodeQ.size();
            for (int i = 0; i < curLevelNodeNum; ++i)
            {
                TreeNode * node = levelNodeQ.front();
                levelNodeQ.pop();

                //the last node in this level
                if (i == curLevelNodeNum - 1)
                {
                    rightSightVals.push_back(node->val);
                }

                if (node->left)
                {
                    levelNodeQ.push(node->left);
                }

                if (node->right)
                {
                    levelNodeQ.push(node->right);
                }
            }
        }

        return rightSightVals;
    }
};

/*
recursive solution:
recursively traverse by level,record the right side of every level
*/

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        traverseByLevel(root,0);
        return rightSideVals;
    }
private:
    //this recursive traverse is a kind of preorder traverse
    //dfs 
    void traverseByLevel(TreeNode * root,int level)
    {
        if (!root)
        {
            return;
        }
        
        // printf("traverseByLevel val:%d\n",root->val);
        
        //this level's value has been recorded,just keep update
        if (level < rightSideVals.size())
        {
            rightSideVals[level] = root->val;
        }
        //this level's node value has not been recorded
        //push the first value
        else
        {
            rightSideVals.push_back(root->val);
        }
        
        traverseByLevel(root->left,level + 1);
        traverseByLevel(root->right,level + 1);
    }
private:
    vector<int> rightSideVals;
};
